package test3;

/**
 *   给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 *   如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *输入: nums = [1,3,5,6], target = 5
 *输出: 2
 *输入: nums = [1,3,5,6], target = 7
 *输出: 4
 */
public class Test3 {
    public static void main(String[] args) {
          int[] nums = {1,3,5,6};
          int target = 0;
          int index = findIndex(nums, target);
        System.out.println(index);
    }

    private static int findIndex(int[] nums, int target) {
        //1. 取出数组的中间值 与目标值进行比较,如果相等，直接返回中间值索引
        //2. 中间值<目标值，取右半边的中间值与目标值比较，否则取左半边
        //3. 如果区间只剩下一个元素，目标值比他大，则放在最后一位， 比他小，则放在前一位
        int right = nums.length - 1;
        int left = 0;
        while (left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] == target){
                return mid;
            }else if (target > nums[mid]){
                left = mid + 1;
            }else if (target < nums[mid]){
                right = mid - 1;
            }
        }
        return left;
    }

}
